package main.tree;


import java.util.Iterator;

/**
 * @author lzh
 * @description
 * @date 2021/3/1
 */
public class BST implements Iterable<TreeNode> {
    private TreeNode root;
    private int size;

    /**
     * 检查是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 返回当前容器的长度
     *
     * @return
     */
    public int size() {
        return size;
    }


    /**
     * 二叉搜索树 添加一个元素，如果值已存在，则直接返回
     *
     * @param value
     */
    public void add(int value) {
        TreeNode p = null, cur = root;
        while (cur != null) {
            if (value < cur.value) {
                p = cur;
                cur = cur.left;
            } else if (cur.value < value) {
                p = cur;
                cur = cur.right;
            } else {
                return;
            }
        }
        if (p == null) {
            root = new TreeNode(value);
        } else if (value < p.value) {
            p.left = new TreeNode(value);
            p.left.parent = p;
        } else if (p.value < value) {
            p.right = new TreeNode(value);
            p.right.parent = p;
        }
        ++size;
    }

    /**
     * 检查二叉搜索树是否包含value
     *
     * @param value
     * @return
     */
    public boolean contains(int value) {
        return get(value) != null;
    }

    /**
     * 搜索值=value的节点并返回该节点
     *
     * @param value
     * @return
     */
    public TreeNode get(int value) {
        TreeNode cur = root;
        while (cur != null) {
            if (value < cur.value) {
                cur = cur.left;
            } else if (cur.value < value) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

    /**
     * 二叉搜索树删除value
     *
     * @param value
     */
    public void remove(int value) {
        TreeNode toDelete = get(value);
//        找不到该值
        if (toDelete == null) {
            return;
        }
//        被删除节点是根节点
        if (toDelete.parent == null) {
            --size;
            root = null;
            return;
        }
        while (true) {
//        叶子节点
            if (toDelete.left == null && toDelete.right == null) {
                if (toDelete == toDelete.parent.left) {
                    toDelete.parent.left = null;
                } else {
                    toDelete.parent.right = null;
                }
                break;
            }
//        左右孩子都不空
            if (toDelete.left != null && toDelete.right != null) {
//            找后继节点，一定not null
                TreeNode next = getSuccFromRight(toDelete);
                toDelete.value = next.value;
                toDelete = next;
//            只有右侧节点，用右侧节点代替
            } else if (toDelete.left == null) {
//                被删节点是父节点的左孩子
                if (toDelete == toDelete.parent.left) {
                   replace(toDelete, toDelete.right, "l");
                } else {
                    replace(toDelete, toDelete.right, "r");
                }
                break;
//            只有左侧节点，用左侧节点代替
            } else {
//                被删节点是父节点的右孩子
                if (toDelete == toDelete.parent.right) {
                    replace(toDelete, toDelete.left, "r");
//                被删节点是父节点的左孩子
                } else {
                    replace(toDelete, toDelete.right, "l");
                }
                break;
            }
        }
        --size;
    }

    /**
     *
     * 用childNode取代toDelete节点(childNode必须是toDelete的直接孩子节点)， at="l"表示toDelete是原父节点的左节点，at="r"表示toDelete是原父节点的右节点
     * @param childNode
     * @param at
     */
    private void replace(TreeNode toDelete, TreeNode childNode, String at) {
        if ("l".equals(at)) {
            toDelete.parent.left = childNode;
        } else if ("r".equals(at)) {
            toDelete.parent.right = childNode;
        }
        childNode.parent = toDelete.parent;
    }

    /**
     * 在parent的右子树中找parent的后继节点，如果parent是null。则假设parent是一个虚拟节点，它的右孩子是root节点
     *
     * @param parent
     * @return
     */
    private TreeNode getSuccFromRight(TreeNode parent) {
        TreeNode cur;
        if (null == parent) {
            cur = root;
        } else {
            cur = parent.right;
        }
        if (cur == null) {
            return null;
        }
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur;
    }

    public void traverse() {
        traverse(root);
    }
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        traverse(root.left);
        System.out.println(root.value);
        traverse(root.right);
    }

    @Override
    public Iterator<TreeNode> iterator() {
        return new Iterator<TreeNode>() {
            private TreeNode cur = root;

            @Override
            public boolean hasNext() {
                return cur != null;
            }

            @Override
            public TreeNode next() {
//                Morris中序遍历
                if (!hasNext()) {
                    return null;
                }
                TreeNode tmp = null;
                TreeNode mostRight;
                while (tmp == null) {
                    mostRight = cur.left;
//                    左孩子节点为空，已经可以访问cur节点了
                    if (mostRight == null) {
                        tmp = cur;
                        cur = cur.right;
                    } else {
                        while (mostRight.right != null && mostRight.right != cur) {
                            mostRight = mostRight.right;
                        }
                        if (mostRight.right == null) {
//                        第一次经过cur时，将mostRight的右指针线索化，指向后继节点，即cur自己
                            mostRight.right = cur;
                            cur = cur.left;
                        } else {
//                        第二次经过cur时才会跳转到此处，将mostRight的线索指针还原
                            mostRight.right = null;
                            tmp = cur;
                            cur = cur.right;
                        }
                    }
                }
                return tmp;
            }
        };
    }

}
